// 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

// get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
// put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。
// 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

//  

// 进阶：
// 你是否可以在 O(1) 时间复杂度内执行两项操作？

//  

// 示例：

// LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

// cache.put(1, 1);
// cache.put(2, 2);
// cache.get(1);       // 返回 1
// cache.put(3, 3);    // 去除 key 2
// cache.get(2);       // 返回 -1 (未找到key 2)
// cache.get(3);       // 返回 3
// cache.put(4, 4);    // 去除 key 1
// cache.get(1);       // 返回 -1 (未找到 key 1)
// cache.get(3);       // 返回 3
// cache.get(4);       // 返回 4

#include "stdc++.h"

/* 哈希表 + 平衡二叉树
c++中用set作为平衡二叉树
时间复杂度：
    get -- O(logN)
    put -- O(logN)
空间复杂度：
    O(capacity)
*/
class LFUCache {
private:
    struct Node {
        int cnt{}; // 使用频率
        int time{}; // 缓存的使用时间
        int key{};
        int value{};
        Node(int _cnt, int _time, int _key, int _value) : cnt(_cnt), time(_time), key(_key), value(_value) {}
        bool operator < (const Node& rhs) const {
            return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;
        }
    };
    int m_capacity{}; // 缓存容量
    int m_time{0}; // 时间戳
    unordered_map<int, Node> m_hashTable{};
    set<Node> m_set{};
public:
    LFUCache(int capacity) : m_capacity(capacity) {}
    
    int get(int key) {
        if (m_capacity == 0) {
            return -1;
        }
        auto it = m_hashTable.find(key);
        if (it == m_hashTable.end()) {
            return -1;
        }
        // 从哈希表中得到旧的缓存
        Node cache = it->second;
        // 从平衡二叉树中删除旧缓存
        m_set.erase(cache);
        // 更新旧缓存
        cache.cnt += 1;
        cache.time = ++m_time;
        // 将新缓存重新放入哈希表和平衡二叉树中
        m_set.insert(cache);
        it->second = cache;
        return cache.value;
    }
    
    void put(int key, int value) {
        if (m_capacity == 0) {
            return;
        }
        auto it = m_hashTable.find(key);
        if (it == m_hashTable.end()) {
            // 如果达到缓存上限
            if (m_hashTable.size() == m_capacity) {
                // 从哈希表和平衡二叉树中删除最近最少使用的缓存
                m_hashTable.erase(m_set.begin()->key);
                m_set.erase(m_set.begin());
            }
            // 创建新的缓存
            Node cache = Node(1, ++m_time, key, value);
            // 将新的缓存放进哈希表和平衡二叉树中
            m_hashTable.insert(make_pair(key, cache));
            m_set.insert(cache);
        } else {
            Node cache = it->second;
            m_set.erase(cache);
            cache.cnt += 1;
            cache.time = ++m_time;
            cache.value = value;
            m_set.insert(cache);
            it->second = cache;
        }
    }
};

/* 双哈希表
时间复杂度：
    get -- O(1)
    put -- O(1)
空间复杂度：
    O(capacity)
*/
class LFUCache {
private:
    struct Node {
        int key{};
        int val{};
        int freq{};
        Node(int _key, int _val, int _freq) : key(_key), val(_val), freq(_freq) {} 
    };
    int m_minFreq{0};
    int m_capacity{};
    unordered_map<int, list<Node>::iterator> m_keyTable{};
    unordered_map<int, list<Node>> m_freqTable{};
public:
    LFUCache(int capacity) : m_capacity(capacity) {}
    
    int get(int key) {
        if (m_capacity == 0) {
            return -1;
        }
        auto it = m_keyTable.find(key);
        if (it == m_keyTable.end()) {
            return -1;
        }
        auto node = it->second;
        int val = node->val;
        int freq = node->freq;
        m_freqTable[freq].erase(node);
        // 如果当前链表为空，我们需要在哈希表中删除，且更新m_minFreq
        if (m_freqTable[freq].size() == 0) {
            m_freqTable.erase(freq);
            if (m_minFreq == freq) {
                m_minFreq += 1;
            }
        }
        // 插入到freq + 1中
        m_freqTable[freq + 1].push_front(Node(key, val, freq + 1));
        m_keyTable[key] = m_freqTable[freq + 1].begin();
        return val;
    }
    
    void put(int key, int value) {
        if (m_capacity == 0) {
            return;
        }
        auto it = m_keyTable.find(key);
        if (it == m_keyTable.end()) {
            // 缓存已满，需要进行删除操作
            if (m_keyTable.size() == m_capacity) {
                // 通过m_minFreq 拿到 m_freqTable[m_minFreq] 链表的末尾节点
                auto it2 = m_freqTable[m_minFreq].back();
                m_keyTable.erase(it2.key);
                m_freqTable[m_minFreq].pop_back();
                if (m_freqTable[m_minFreq].size() == 0) {
                    m_freqTable.erase(m_minFreq);
                }
            }
            m_freqTable[1].push_front(Node(key, value, 1));
            m_keyTable[key] = m_freqTable[1].begin();
            m_minFreq = 1;
        } else {
            // 与get操作基本一致，除了需要更新缓存的值
            auto node = it->second;
            int freq = node->freq;
            m_freqTable[freq].erase(node);
            if (m_freqTable[freq].size() == 0) {
                m_freqTable.erase(freq);
                if (m_minFreq == freq) {
                    m_minFreq += 1;
                }
            }
            m_freqTable[freq + 1].push_front(Node(key, value, freq + 1));
            m_keyTable[key] = m_freqTable[freq + 1].begin();
        }
    }
};
